#include <iostream>
#include <string>
#include <vector>
using namespace std;
    
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
 };
 
class Solution {
public:

    ListNode* Node_reverse(ListNode* head)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = Node_reverse(head1);
        head2 = Node_reverse(head2);
        int val = 0;
        ListNode* cur1 = head1;
        ListNode* cur2 = head2;
        ListNode* head = nullptr;
        ListNode* prev = nullptr;
        while (cur1 || cur2)
        {
            ListNode* cur = new ListNode(0);
            if (cur1 == nullptr)
            {
                cur->val = (cur2->val + val) % 10;
                val = (cur2->val + val) / 10;
                cur2 = cur2->next;
            }
            else if (cur2 == nullptr)
            {
                cur->val = (cur1->val + val) % 10;
                val = (cur1->val + val) / 10;
                cur1 = cur1->next;
            }
            else
            {
                cur->val = (cur2->val + val + cur1->val) % 10;
                val = (cur1->val + val + cur2->val) / 10;
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            if (head == nullptr)
            {
                head = prev = cur;
            }
            prev->next = cur;
            prev = prev->next;
        }
        if (val != 0)
        {
            ListNode* cur = new ListNode(val);
            prev->next = cur;
        }
        return Node_reverse(head);
    }
};

class Solution {
public:
    string solve(string s, string t) {
        // write code here
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        int val = 0;
        string str;
        int i = 0;
        while (s[i] && t[i])
        {
            int a = s[i] - '0';
            int b = t[i] - '0';
            str += ((a + b + val) % 10 + '0');
            val = (a + b + val) / 10;
            i++;
        }
        while (s[i])
        {
            int a = s[i] - '0';
            str += ((a + val) % 10 + '0');
            val = (a + val) / 10;
            i++;
        }
        while (t[i])
        {
            int a = t[i] - '0';
            str += ((a + val) % 10 + '0');
            val = (a + val) / 10;
            i++;
        }
        if (val)
        {
            str += (val + '0');
        }
        reverse(str.begin(), str.end());
        return str;
    }
};


class Solution {
public:
    string solve(string s, string t) {
        // write code here
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        int n = s.size();
        int m = t.size();
        vector<int> tmp(m + n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                tmp[i + j] += ((s[i] - '0') * (t[j] - '0'));
            }
        }
        int val = 0;
        string ret;
        for (auto tt : tmp)
        {
            ret += ((val + tt) % 10 + '0');
            val = (val + tt) / 10;
        }
        while (val)
        {
            ret += (val % 10 + '0');
            val /= 10;
        }
        while (ret.size() > 1 && ret.back() == '0')
        {
            ret.pop_back();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    ListNode* ListAdd(ListNode* head1, ListNode* head2) {
        // write code here
        int val = 0;
        ListNode* cur1 = head1;
        ListNode* cur2 = head2;
        ListNode* head = nullptr;
        ListNode* prev = nullptr;
        while (cur1 || cur2)
        {
            ListNode* cur = new ListNode(0);
            if (cur1 == nullptr)
            {
                cur->val = (cur2->val + val) % 10;
                val = (cur2->val + val) / 10;
                cur2 = cur2->next;
            }
            else if (cur2 == nullptr)
            {
                cur->val = (cur1->val + val) % 10;
                val = (cur1->val + val) / 10;
                cur1 = cur1->next;
            }
            else
            {
                cur->val = (cur2->val + val + cur1->val) % 10;
                val = (cur1->val + val + cur2->val) / 10;
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            if (head == nullptr)
            {
                head = prev = cur;
            }
            prev->next = cur;
            prev = prev->next;
        }
        if (val != 0)
        {
            ListNode* cur = new ListNode(val);
            prev->next = cur;
        }
        return head;
    }
};